\documentclass[a4paper,10pt]{article}
\usepackage[spanish]{babel}
\usepackage{amsfonts}
\usepackage{algorithm2e}
\usepackage{listings}
\lstset{ %
			language=Python,
			basicstyle=\footnotesize,
			numbers=left,
			stepnumber=1,
			numbersep=4pt,
			tabsize=2,
}

\title{Problema del perfil de la ciudad}
\author{
        Ignacio Garay \\
                \and
        Ariel Liguori\\
        	\and
	Pablo Musumeci
}
\date{\today}

\begin{document}
\maketitle

\begin{abstract}
El presente es un an\'alisis sobre el problema de obtenci\'on del perfil de la ciudad mediante una soluci\'on algor\'itmica que emplea la t\'ecnica de dividir y conquistar y abarca el an\'analisis de complejidad del mismo.


\section{Introducci\'on}\label{intro}
El problema de obtenci\'on del perfil de la ciudad se abordar\'a dada una lista de edificios representados por una terna $(x_1, h_1, x_2)$ en la cual $x_1$ representa el la posici\'on de inicio del edificio, $x_2$ el final y $h_1$ la altura del mismo. Para la resoluci\'on se emplear\'a un algoritmo que emplee la t\'ecnica de Dividir y Conquistar y se analizar\'a la complejidad algor\'itmica del mismo. La soluci\'on estar\'a dada por un conjunto de pares $(x_i, y_i)$ dipuestos en orden de izquierda a derecha.

\newpage
\section{Planteo}\label{planteo}
El planteo algor\'itmico del problema se basa en la t\'ecnica de dividir y conquistar \cite{divideConquer} con la cual tendremos esencialmente tres pasos b\'asicos:

\begin{enumerate}
\item Divide - Consiste en efectivamente dividir el problema en otros menores.
\item Conquer - Efectuar la soluci\'on a los problemas peque\~nos.
\item Merge - Unir las soluciones peque\~nas en una \'unica soluci\'on general.
\end{enumerate}

El tama\~no del problema esta dado por la cantidad de edificios de entrada que reciba nuestro algoritmo, $(n)$.

La soluci\'on se obtendr\'a empleando la soluci\'on a cada uno de los siguientes escenarios:

\begin{enumerate}
\item \textbf{Caso Base}
\\
Dado que la entrada se encuentra limitada al tama\~no de la entrada, el caso base estar\'a dado por el caso en el que se encuentre un \'unico edificio. La soluci\'on ante ese caso ser\'a:


\begin{algorithm}[H]
	\SetAlgoLined
	\KwData{Buildings[1..1]}
	\KwResult{ Lista soluci\'on }
	$Skyline = { (Buildings[1].x_1 , Buildings[1].h_1) , (Buildings[1].x_2 , 0) }$;

	return $Skyline$;

\end{algorithm}

\item \textbf{Divide} 
\\
En general cualquier t\'ecnica de divisi\'on del tama\~no de la entrada ser\'ia de utilidad, no obstante y teniendo en cuenta el posterior an\'alisis de la complejidad del algorimo propondremos una divisi\'on en partes de igual tama\~no.

\item \textbf{Merge}
\\
\\
Un m\'etodo para unir dos perfiles cualesquiera v\'alidos puede ser realizado de la siguiente forma:
\begin{itemize}
\item Un punto $(x_i,y_i)$ es agregado a una lista soluci\'on vac\'ia.
\item Se asigna $x = min {x_1, x_2}$, lo que representa la posici\'on horizontal que se encuentra emplazada m\'as a la izquierda.
\item Se asigna la altura m\'axima de los dos edificios analizados, max(h_1,h_2).

\end{itemize}
\end{enumerate}

\newpage
\section{An\'alisis de complejidad}\label{analisis}

Para el an\'alisis de complejidad nos basaremos en el algoritmo final propuesto seg\'un lo indicado en el punto anterior(planteo):

\subsection{Skyline (Divide)}
\begin{algorithm}[H]
	\KwData{Buildings[1..n]}
	\KwResult{ Lista soluci\'on: Skyline }
	\If{ n == 1}{
		return SolucionCasoBase(Buildings);
	}
	Skyline_1 = Skyline(Buildings[1..n/2]);\\
	Skyline_2 = Skyline(Buildings[n/2..n]);\\
	Skyline = merge(Skyline_1, Skyline_2);\\
	return Skyline;\\

\end{algorithm}

\subsection{MergeSkyline (Merge)}
\begin{algorithm}[H]
	\KwData{Skyline_1, Skyline_2}
	\KwResult{ Lista soluci\'on: Skyline }
	$Skyline \leftarrow 0$\;
	$CurH_1 \leftarrow 0$\;
	$CurH_2 \leftarrow 0$\;
	\While{Skyline_1 \neq \emptyset and Skyline_2 \neq \emptyset}{
		\If{head_1.x_1 menor head_2.x_1 }{
			CurH_1 \leftarrow head_1.h_1\\
			CurX \leftarrow head_1.x_1\\
			Skyline \leftarrow (CurX, Max(CurH_1, CurH_2))\\
			\Else{
			CurH_2 \leftarrow head_2.h_1\\
			CurX \leftarrow head_2.x_1\\
			Skyline \leftarrow (CurX, Max(CurH_1, CurH_2))\\
			}
		}
	}\\
\end{algorithm}
\begin{algorithm}[H]
	\If{Skyline_1 == \emptyset }{
		Skyline \leftarrow Skyline_2\\
		\Else{
		Skyline \leftarrow Skyline_1\\
		}
	}\\

	return Skyline\;
\end{algorithm}

Seg\'un lo aqu\'i expuesto podemos definir la compejidad de cada paso que nos permite obtener la soluci\'on, con lo cual:

\begin{enumerate}
\item La divisi\'on del problema en dos sets = $\Theta(1)$
\item Resoluci\'on de cada mitad = $T(n/2)$
\item Merge de las soluciones en $\Theta(n)$
\end{enumerate}

Obteniendo de (1), (2) y (3) \begin{equation}T(n) = 2T(n/2)+ \Theta(n)\end{equation}
Finalmente, \begin{equation}\Theta(n logn)\end{equation}

\subsection{An\'alisis implementaci\'on}
A continuaci\'on se detalla el an\'alisis directamente sobre la implementaci\'on de la soluci\'on propuesta:

\begin{lstlisting}
def skyline(buildings):

	if len(buildings) == 1:
		keypoints= []
		keypoints.append((buildings[0][LEFT],buildings[0][HEIGHT]))
		keypoints.append((buildings[0][RIGHT],0))
		return keypoints

	keypoints = []
	ListA = skyline(buildings[(len(buildings)/2):])
	ListB = skyline(buildings[:(len(buildings)/2)])
	
	CurrentHeightA = 0
	CurrentHeightB = 0
	CurrentX = 0

	while ListA and ListB:
		
		elemA = ListA[0]
		elemB = ListB[0]

		if  elemA[LEFT] < elemB[LEFT]:
			CurrentHeightA = elemA[HEIGHT]
			CurrentX = elemA[LEFT]
			keypoints.append((CurrentX, max(CurrentHeightA,CurrentHeightB)))	
			del ListA[0]
		else:
			CurrentX = elemB[LEFT]
			CurrentHeightB = elemB[HEIGHT]
			keypoints.append((CurrentX, max(CurrentHeightA,CurrentHeightB)))
			del ListB[0]

	if not ListA:
		while ListB:
			elemB = ListB[0]
			keypoints.append(elemB)
			del ListB[0];
			
	if not ListB:
		while ListA:
			elemA = ListA[0]
			keypoints.append(elemA)
			del ListA[0];
	return keypoints

def mergeBuildings(buildings):
	actualHeight = 0
	builds = []
	for i in buildings:
		if i[HEIGHT] != actualHeight:
			builds.append(i)
			actualHeight = i[HEIGHT]
	return builds
\end{lstlisting}

Seg\'un se puede observar la implementaci\'on responde al algoritmo descripto en la secci\'on de planteo, con lo cual para proceder con la afirmaci\'on de que la complejidad anteriormente detallada corresponde a la de nuestro desarrollo deberemos destacar en profundidad el orden de complejidad de las operaciones sobre listas de Python \cite{pythonTime}.

\subsection{Complejidad algor\'itmica de listas}
El an\'alisis que se realiza a continuaci\'on responde a lo detallado por la documentaci\'on oficial del lenguaje de programaci\'on Python \cite{pythonTime}. En particular en nuestro trabajo deberemos ahondar en la complejidad de las siguientes operaciones:

\begin{itemize}
\item append
\item Get item
\item Set item
\end{itemize}

Dichas operaciones seg\'un lo indicado en las referencias son realizadas en un tiempo de $\Theta(1)$. Con esta consideraci\'on podemos afirmar que la complejidad del algoritmo que hemos implementado responde a lo detallado en la secci\'on de planteo y es por tanto $\Theta(n logn)$.

\newpage

\section{Referencias}\label{referencias}
\begin{thebibliography}{9}
\bibitem{pythonTime}
  Python Information Wiki Documentation,
  \emph{Time Complexity: Python time complexity of basic structures}.
  http://wiki.python.org/moin/TimeComplexity

\bibitem{divideConquer}
  Divide and conquer base information.
  \emph{http://en.wikipedia.org/wiki/Divide_and_conquer}.
  Wikipedia, 2012.

\end{thebibliography}

\newpage
\section{Anexo}\label{anexo}
\subsection{skyline.py}
\lstinputlisting{skyline.py}
\newpage
\tableofcontents


\end{document}
